package cacy.leetcode.linkedList;

/**
 * Project: LeetcodePractice
 * Package: cacy.leetcode.practice20250217
 * Class:   LinkedList04
 * Description:
 * 给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。
 *
 * 示例 1：
 * 输入：head = [2,4,7,8], cnt = 1
 * 输出：8
 *
 * 提示：
 *     1 <= head.length <= 100
 *     0 <= head[i] <= 100
 *     1 <= cnt <= head.length
 *
 * @Date: 2025/2/17 周一
 * @Time: 15:09
 * @Author: 凯齐
 */

// Use two nodes, one fast and one slow, let them move forward simultaneously
class Solution04A {
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode nodeLow = head;
        ListNode nodeFast = nodeLow;
        for (int i = 0; i < cnt; i++) {
            nodeFast = nodeFast.next;
        }
        while (nodeFast != null) {
            nodeLow = nodeLow.next;
            nodeFast = nodeFast.next;
        }
        return nodeLow;
    }
}

// Use one node and it only traverses the difference
// between the total number of nodes and the number counting from the end.
class Solution04B {
    public ListNode trainingPlan(ListNode head, int cnt) {
        int total = 0;
        ListNode tmp = head;
        while (tmp != null) {
            total++;
            tmp = tmp.next;
        }
        for (int i = 0; i < total - cnt; i++) {
            head = head.next;
        }
        return head;
    }
}

public class LinkedList04 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.push(2);
        head.push(3);
        head.push(4);
        ListNode res = new Solution04B().trainingPlan(head, 4);
        System.out.println(res.val);
    }
}
